package com.fyl.leetcode.dynamic;

/**
 * @author:fyl
 * @date 2021/8/4 8:37
 * @Modified By:
 * @Modified Date:
 * @Description: 343
 * 给定一个正整数n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
 * 示例 1:
 * 输入: 2
 * 输出: 1
 * 解释: 2 = 1 + 1, 1 × 1 = 1。
 * 这题还可以这样想，对于给定的数 n，F(n)F(n) 表示将 n 分解成多个(≥2)整数的最大乘积，那么有以下几种情况：
 * 1️⃣ 将n分解成两个数:
 *
 * F(n)=i* (n - i),\ (i=1,2,...,n-1)
 * F(n)=i∗(n−i),(i=1,2,...,n−1)
 *
 * 2️⃣ 将n分解成两个以上的数:
 * 也就是说我们要对 i 和 n - i 进一步分解，那么就有三种情况（继续分解其中一个或两个都继续分解），将i和n - i进一步分解的最大乘积分别记为 F(i)F(i)和F(n - i)F(n−i)，那么有：
 *
 * F(n)=max\left\{ \begin{array}{rcl} i * F(n - i) & & {对\ n - i\ 继续分解}\\ F(i) * (n - i) & & {对\ i\ 继续分解}\\ F(i) * F(n- i) & & {对\ i 和\ n - i\ 都继续分解} \end{array} \right.
 * F(n)=max
 * i∗F(n−i)
 * F(i)∗(n−i)
 * F(i)∗F(n−i)
 * 对n−i继续分解
 * 对i继续分解
 * 对i和n−i都继续分解
 * 但是，我们观察上面的表达式，不难发现，当i取遍[1,n-1][1,n−1]时，由于i和n - i的取值对称，
 * i * F(n - i)i∗F(n−i) 和 F(i) * (n - i)F(i)∗(n−i)的取值集合是一样的，也就是说这两种情况算出来的结果是一样的，
 * 所以只取其中一种就可以了。对于F(i)*F(n-i)F(i)∗F(n−i)，其实这种情况也是不用考虑的，因为 i*(n - i)i∗(n−i)和i * F(n - i)i∗F(n−i)已经包含了所有的分解情况了。
 * 那么整个表达式就为：
 * F(n) = max\{ i * (n - i), i * F(n - i)\},\ (i=1,2,...,n-1)
 * F(n)=max{i∗(n−i),i∗F(n−i)},(i=1,2,...,n−1)
 */
public class IntegerBreak {
    public int integerBreak(int n) {
        int[] dp = new int[n + 1];
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= i - 1; j++) {
                dp[i] = Math.max(dp[i], Math.max(j * dp[i - j], j * (i - j)));
            }
        }
        return dp[n];
    }
}
